package com.breeze.leetcode;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/single-number/
 * 136. 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 */
public class LeetCode136 {
    /**
     * 方法一： 先排序再找不同
     * <p>
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i = i + 2) {
            if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * 方法二：异或运算（该方法太过牛逼）
     * <p>
     * 异或3个性质：
     * 1. a 异或 0 = a
     * 2. a 异或 a = 0
     * 3. 异或满足交换率结合率：a 异或 b 异或 a => a 异或 a 异或 b = b
     * 故我们只需要对数组遍历一次进行异或运算，即可消除相同元素
     */
    public int singleNumber2(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

    // 其他方法，使用哈系表也可以完成该题目，但需要额外的空间，比较简单，不再给出

    public static void main(String[] args) {
        LeetCode136 leetCode136 = new LeetCode136();
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println(leetCode136.singleNumber2(nums));
    }
}
